package com.tucc.hello.leetcode.no1_400.no1_200.no21_40.no30;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "barfoothefoobarman";
        String[] words = {"foo", "bar"};
        s = "aaa";
        words = new String[]{"a", "a"};
//        s = "wordgoodgoodgoodbestword";
//        words = new String[]{"word","good","best","word"};
//        s = "aacbbbbbc";
//        words = new String[]{"aa", "cb"};
//        s = "bcabbcaabbccacacbabccacaababcbb";
//        words = new String[]{"c","b","a","c","a","a","a","b","c"};
        s = "abaababbaba";
        words = new String[]{"ba", "ab", "ab"};
        List<Integer> result = solution.findSubstring(s, words);
        System.out.print(result);
    }

    public List<Integer> findSubstring(String s, String[] words) {
        int length = words.length;
        Map<String, Integer> needWords = new HashMap<>();
        for (String word : words) {
            Integer num = needWords.get(word);
            needWords.put(word, num == null ? 1 : num + 1);
        }
        List<Integer> result = new ArrayList<>();
        if (length == 0) {
            return result;
        }
        int oneWordLen = words[0].length();
        length = length * oneWordLen;
        int curStart = 0;
        int curIndex = 0;
        Map<String, Integer> curWords = new HashMap<>();
        while (curStart <= s.length() - length) {
            while (curIndex - curStart < length && curIndex + oneWordLen <= s.length()) {
                String curWord = s.substring(curIndex, curIndex + oneWordLen);
                Integer needNum = needWords.get(curWord);
                curIndex += oneWordLen;
                Integer curNum = curWords.get(curWord);
                curNum = curNum == null ? 1 : curNum + 1;
                if (needNum == null || curNum > needNum) {
                    curStart += 1;
                    curIndex = curStart;
                    curWords.clear();
                } else {
                    curWords.put(curWord, curNum);
                }
            }
            if (curStart <= s.length() - length) {
                result.add(curStart);
                String stWord = s.substring(curStart, curStart + oneWordLen);
                if (oneWordLen == 1) {
                    curStart += oneWordLen;
                    curWords.put(stWord, curWords.get(stWord) - 1);
                } else {
                    curStart += 1;
                    curIndex = curStart;
                    curWords.clear();
                }
            }
        }
        return result;
    }

}
